package algorithm;

import java.util.Arrays;

/**
 * User: Asuka
 * Date: 11-3-28
 * Time: 下午10:26
 */
public class MinimumCommonSequence {

    private static final char[] seq1 = new char[]{0, 'a', 'b', 'e', 'c', 'd'};
    private static final char[] seq2 = new char[]{0, 'a', 'e', 'f', 'c'};

    public static void main(String[] args) {
        MinimumCommonSequence sequence = new MinimumCommonSequence();
        int[][] array = sequence.makeArray(seq1, seq2);
//        System.out.println(Arrays.deepToString(array));
    }

    public int[][] makeArray(char seq[], char anotherSeq[]) {
        int[][] result = new int[seq.length][anotherSeq.length];
        for (int i = 1; i < result.length; i++) {
            for (int j = 1; j < result[0].length; j++) {
                if (seq[i] == anotherSeq[j]) {
                    System.out.print(seq1[i]);
                    result[i][j] = result[i - 1][j - 1] + 1;
                } else if (result[i - 1][j] >= result[i][j - 1]) {
                    result[i][j] = result[i - 1][j];
                } else {
                    result[i][j] = result[i][j - 1];
                }
            }
        }
        return result;
    }
}
